package top100;

/**
 * @author Godc
 * @description
 */
public class Kth {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int s = solution.findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 1);
        System.out.println(s);
    }
}
class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums,0,nums.length-1,k-1);
        return nums[k-1];
    }
    public void quickSort(int[] nums,int left,int right,int k){
        int i = left,j = right;
        int base = nums[(int)Math.random()*(right-left)+left];
        while(i<j){
            while(i<j&&nums[j]<=base) j--;
            while(i<j&&nums[i]>=base) i++;
            if(i<j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[left] = nums[i];
        nums[i] = base;
        if(i<k) quickSort(nums,i+1,right,k);
        if(i>k) quickSort(nums,left,i-1,k);
    }
}
